Selamat datang di Kuliah 2. Setelah menetapkan tujuan keseluruhan untuk kursus ini, kita kini memasuki struktur data dasar yang menjadi fondasi perancangan algoritma: Struktur Datayang membentuk blok-blok dasar dalam perancangan algoritma: Array dan Daftar Berantai.
Array dan Daftar Berantai adalah cara paling dasar dan penting dalam mengatur data di memori, mencerminkan konflik inti antara bersebelahan dan terpisah manajemen penyimpanan.
Definisi:Struktur Data adalah format khusus untuk mengorganisasi dan menyimpan data agar akses dan modifikasi dapat dilakukan secara efisien.
- Array menyimpan elemen dalam bersebelahanlokasi memori, yang memungkinkan perhitungan langsung alamat elemen.
- Daftar Berantai menyimpan elemen dalam terpisahlokasi memori yang terpisah, hanya terhubung melalui pointer eksplisit.
- Akses array adalah Pengindeksan Langsung ($O(1)$), sedangkan akses daftar berantai membutuhkan Traversing ($O(n)$).
- Operasi sisipan/hapus pada array membutuhkan penggeseran elemen, menghasilkan kompleksitas $O(n)$ kompleksitas.
- Operasi sisipan/hapus pada daftar berantai hanya membutuhkan Relinking Pointer, mencapai $O(1)$ jika posisi $i$ diketahui.
- Daftar berantai menimbulkan beban ruang yang lebih tinggi karena setiap node harus menyimpan data ditambah pointer `next`.Beban Ruangkarena setiap node harus menyimpan data ditambah pointer `next`.
Perbandingan Kompleksitas
| Fitur | Array | Daftar Berantai Sederhana |
|---|---|---|
| Alokasi Memori | Bersebelahan (Ukuran Blok Tetap $n$) | Terpisah (Pointer Dinamis) |
| Waktu Akses | $O(1)$ | $O(n)$ |
| Sisipan/Hapus | $O(n)$ | $O(1)$ (jika posisi $i$ diketahui) |
| Beban Ruang | Minimal (hanya data) | Tinggi (data + next pointer) |